package com.ting.test.algorithms.滑动窗口;

import java.util.LinkedList;

/**
 * Created by 雷霆 on 2020/11/6.
 * <p>
 * Description：
 * 假设一个固定大小为W的窗口，依次划过arr，
 * 返回每一次滑出状况的最大值
 * 例如，arr = [4,3,5,4,3,3,6,7], W = 3
 * 返回：[5,5,5,4,6,7]
 */
public class 固定窗口解法2 {

    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
        int w = 3;
        int[] result = fun(arr, w);
        for (int res : result) {
            System.out.println(res);
        }

    }

    private static int[] fun(int[] arr, int w) {
        //根据题意可知，一共会产生arr.length-w+1个最大值
        int[] result = new int[arr.length - w + 1];
        int index = 0;
        //定义一个单调递减的（由大到小）双端队列
        LinkedList<Integer> window = new LinkedList();
        int L = 0, R = 0;//采用左闭右开策略[L,R]

        //先固定左边
        while (L <= R && R < arr.length) {
            //更新结构是单调递减
            //该行的目的是 当更新结构不为空，并且当前下标R代表的元素>=更新结构尾部元素时，为了保证更新结构的单调递减性
            //需要将更新结构的尾部元素弹出
            while (!window.isEmpty() && arr[R] >= arr[window.peekLast()]) {
                window.pollLast();
            }
            //当该while循环结束时，意味着，1.windows为空,
            window.addLast(R);//在尾部添加新的元素下标
            //当
            //添加完元素之后，看当前滑动窗口是否已经满足W，如果满足，则需要记录当前窗口内的最大值
            if (R - L + 1 >= w) {
                //当滑动窗口长度满足W时，更新结构内的头部元素就是当前窗口内的最大值
                result[index++] = arr[window.peekFirst()];
                L++;
                if (L - 1 == window.peekFirst()) {
                    window.pollFirst();
                }

            }
            R++;
        }

        return result;
    }

}
